package com.ly.test;

import org.junit.jupiter.api.Test;

import java.util.*;


/**
 * @Classname T
 * @Description TODO
 * @Date 2020/9/15 10:47
 * @Author 冷心影翼
 */
public class T {


	public static void main(String[] args)  {

	}

	@Test
	public void bubbleSort() {
		int[] arr = new int[]{1,2,33,-2,4,22,55,33,55,4,3,2};

        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr.length - i - 1; j++) {
                if(arr[j] > arr[j+1]) {
                    int temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
            }
        }

        System.out.println(Arrays.toString(arr));
    }


    @Test
    public void quickSort() {
        int[] arr = new int[]{1,2,33,-2,4,22,55,33,55,4,3,2};
        quickSort(0,arr.length-1,arr);
        System.out.println(Arrays.toString(arr));
    }

    public void quickSort(int left,int right,int[] arr) {
	    if(left>=right) {
	        return;
        }
        int i = left;
	    int j = right;
	    int p = arr[left];
	    while (i<j) {
	        while (i<j && arr[j]>p) {
	            j--;
            }
            arr[i] = arr[j];
	        while (i<j && arr[i]<=p) {
	            i++;
            }
            arr[j] = arr[i];
        }
        arr[i] = p;
	    quickSort(left,i-1,arr);
	    quickSort(i+1,right,arr);
    }

    @Test
    public void mergeSort() {
        int[] arr = new int[]{1,2,33,-2,4,22,55,33,55,4,3,2};
        int[] temp = new int[arr.length];
        mergeSort(arr,0,arr.length-1,temp);
        System.out.println(Arrays.toString(arr));
    }

    private void mergeSort(int[] arr, int left, int right, int[] temp) {
	    if(left>=right) {
	        return;
        }

        int mid = (left+right)/2;
	    mergeSort(arr,left,mid, temp);
	    mergeSort(arr,mid+1,right, temp);
	    merge(arr,left,mid,right,temp);
    }

    private void merge(int[] arr, int left, int mid, int right,int[] temp) {
        int l = left;
        int m = mid+1;
        int t = 0;

        while (l<=mid && m<=right) {
            if(arr[l]<=arr[m]) {
                temp[t++] = arr[l++];
            }else {
                temp[t++] = arr[m++];
            }
        }

        while (l<=mid) {
            temp[t++] = arr[l++];
        }
        while (m<=right) {
            temp[t++] = arr[m++];
        }

        t = 0;
        for (int i = left; i <= right; i++) {
            arr[i] = temp[t++];
        }


    }

    @Test
    public void heapSort() {
        int[] arr = new int[]{1,2,33,-2,4,77,55,33,55,4,3,2};
        for (int i = arr.length/2; i >= 0 ; i--) {
            fixDown(arr,i,arr.length);
        }

        for (int i = arr.length-1; i > 0 ; i--) {
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;
            fixDown(arr,0,i);
        }

        System.out.println(Arrays.toString(arr));
    }

    public void fixDown(int[] arr, int i, int size) {
	    int l = i*2+1;
	    int r = i*2+2;
	    int largest = i;
	    if(l<size && arr[l]>arr[largest]) {
	        largest = l;
        }
        if(r<size && arr[r]>arr[largest]) {
            largest = r;
        }
        if (largest!=i) {
            int temp = arr[largest];
            arr[largest] = arr[i];
            arr[i] = temp;
            fixDown(arr,largest,size);
        }
    }
}
